//
//  LAGMapView+ClusterMake.m
//  LAMapBasicDemo
//
//  Created by 罗亮富 on 2017/7/1.
//  Copyright © 2017年 2Bulu. All rights reserved.
//



#import "LAGMapView.h"
#import <objc/runtime.h>
#import "LAGClusterAnnotation.h"
#import "LAGMapProtocol.h"

#define SCALED_ZOOM_DELTA 0.2
#define MAP_EXTENTION_DELTA_WIDTH (self.frame.size.width/4.0)
#define MAP_EXTENTION_DELTA_HEIGHT (self.frame.size.height/4.0)

#pragma mark- c functions
static inline bool isCoordinateInRegion(CLLocationCoordinate2D coordinate, MKCoordinateRegion region)
{
    CLLocationDegrees latMax = region.center.latitude + region.span.latitudeDelta/2;
    CLLocationDegrees latMin = region.center.latitude - region.span.latitudeDelta/2;
    CLLocationDegrees lngMax = region.center.longitude + region.span.longitudeDelta/2;
    CLLocationDegrees lngMin = region.center.longitude - region.span.longitudeDelta/2;
    
    if((coordinate.latitude >= latMin && coordinate.latitude <= latMax)
       && (coordinate.longitude >= lngMin && coordinate.longitude <= lngMax))
    {
        return true;
    }
    
    return false;
}

#pragma mark- --------------NSObject (AnnotationGroupIdentifier)----------------------

@interface NSObject (AnnotationGroupIdentifier)

@property (nonatomic, strong) NSString *clusterGroupID;

@end

@implementation NSObject (AnnotationGroupIdentifier)

static char grpIdKey;
-(void)setClusterGroupID:(NSString *)clusterGroupID
{
    objc_setAssociatedObject(self, &grpIdKey, clusterGroupID, OBJC_ASSOCIATION_RETAIN_NONATOMIC);
}

-(NSString *)clusterGroupID
{
    return objc_getAssociatedObject(self, &grpIdKey);
}

@end

#pragma mark- LAGClusterAnnotation (INTERNAL)

@interface LAGClusterAnnotation ()

-(void)addChildAnnotations:(NSArray <id<MKAnnotation>> *)annotations;
-(void)removeChildAnnotations:(NSArray <id<MKAnnotation>> *)annotations;

@end


#pragma mark- ---------------------LAGMapView (ClusterMake)-----------------------------



/*
 cluster计算逻辑：
 1、不在(潜在)可视区域范围内的annotation，把他们添加到临时数组中不添加到地图
 2、在（潜在）可视区域内的点做cluster运算 然后再添加到地图
 
 */

@implementation LAGMapView (ClusterMake)

#pragma mark- getter/setter
-(void)setAnnotationClusteringRadium:(CGFloat)annotationClusteringRadium
{
    BOOL needRefresh = NO;
    if(fabs(annotationClusteringRadium - _clusterRadium) > 10)
        needRefresh = YES;
    
    _clusterRadium = annotationClusteringRadium;
    
    if(needRefresh)
        [self refreshAnnotationCluster];
}

-(CGFloat)annotationClusteringRadium
{
    return _clusterRadium;
}



#pragma mark- cluster calculate

-(nullable NSArray<id<MKAnnotation>> *)filtOutVisableAnnotationsFromSource:(nonnull NSArray<id<MKAnnotation>> *)srcAnnotations
                                                               inMapRegion:(MKCoordinateRegion)region
{
    NSMutableArray *ma = [NSMutableArray arrayWithCapacity:srcAnnotations.count];
    
    for(id<MKAnnotation> a in srcAnnotations)
    {
        if(isCoordinateInRegion(a.coordinate,region))
        {
            [ma addObject:a];
        }
    }
    
    if(ma.count > 0)
        return ma;
    else
        return nil;
}


//对annotation做cluster运算,返回
-(nullable NSArray<id<MKAnnotation>> *)clusterForOffMapAnnotations:(nonnull NSArray <id<MKAnnotation>>*)annotations
                                                   forClusterGroup:(nonnull NSString *)groupIdentifier
{
    if(annotations.count == 0)
        return nil;
    
    
    NSMutableArray *groupArray = [NSMutableArray arrayWithCapacity:30];
    
    NSUInteger c = annotations.count;
    NSMutableArray *tempOrgAnns = [NSMutableArray arrayWithArray:annotations];
    
    NSMutableArray *clusterHolder = [NSMutableArray arrayWithCapacity:10];//循环使用，每一次遍历都重新添加
    for(NSUInteger i = 0; i < c; i++)
    {
        [clusterHolder removeAllObjects];
        id<MKAnnotation> fixedAnn = [tempOrgAnns objectAtIndex:i];
        [clusterHolder addObject:fixedAnn];
        
        for(NSUInteger j = i+1; j < c; )
        {
            id<MKAnnotation> ann = [tempOrgAnns objectAtIndex:j];
            
            if([self isAnnotation:ann closeToAnnotation:fixedAnn])
            {
                [clusterHolder addObject:ann];
                [tempOrgAnns removeObjectAtIndex:j];
                c--;
            }
            else
                j++;
        }
        
        if(clusterHolder.count == 1)//里面只有fixedAnn
            [groupArray addObject:fixedAnn];
        else
        {
            LAGClusterAnnotation *cluster = [[LAGClusterAnnotation alloc]initWithChildAnnotations:clusterHolder groupIdentifier:groupIdentifier];
            [groupArray addObject:cluster];
        }
    }
    
    
    return groupArray;
}

-(void)addAnnotation:(nonnull id<MKAnnotation>)annotation toClusterGroup:(nullable NSString *)groupIdentifier
{
    [self addAnnotations:@[annotation] toClusterGroup:groupIdentifier];
}

-(void)addAnnotations:(nonnull NSArray <id<MKAnnotation>> *)annotations toClusterGroup:(nullable NSString *)groupIdentifier
{
    if(annotations.count == 0)
        return;
    
    if(!groupIdentifier)
    {
        [self addAnnotations:annotations];
    }
    else
    {
        if(![_allClusterGroups containsObject:groupIdentifier])
            [_allClusterGroups addObject:groupIdentifier];
    
        [annotations makeObjectsPerformSelector:@selector(setClusterGroupID:) withObject:groupIdentifier];
        
        [self interAddAnnotations:annotations toClusterGroup:groupIdentifier];
    }
}

//内部使用
-(void)interAddAnnotations:(nonnull NSArray <id<MKAnnotation>> *)annotations
            toClusterGroup:(nonnull NSString *)groupIdentifier
{
    if(annotations.count == 0)
        return;
    
    //MKCoordinateRegion visableRegion = self.region;
    MKCoordinateRegion calculateRegion = [self convertRect:CGRectMake(-MAP_EXTENTION_DELTA_WIDTH, -MAP_EXTENTION_DELTA_HEIGHT, self.frame.size.width+MAP_EXTENTION_DELTA_WIDTH*2, MAP_EXTENTION_DELTA_HEIGHT*2+self.frame.size.height) toRegionFromView:self];
    //需要添加到地图的标注点(在可视区域范围内)
    NSArray *annotationsNeedToAdd = [self filtOutVisableAnnotationsFromSource:annotations inMapRegion:calculateRegion];
    
    NSArray *onMapAnnotations = [self onMapAnnotationsForGroup:groupIdentifier];
    
    //需要新添加到地图的annotation，包括cluster和base
    NSArray *annotaionsToAddOnMap = nil;;
    
    //之前是alone，现在跟新加入的合并成了cluster，这些annoation需要移除,新生成的cluster要将添加
    NSMutableArray *annotationsToRemove = nil;
    
    if(onMapAnnotations.count == 0)//做好cluster计算（最后再添加到地图）
    {
        annotaionsToAddOnMap = [self clusterForOffMapAnnotations:annotationsNeedToAdd forClusterGroup:groupIdentifier];
    }
    else //首先以已经在地图上显示的同一identifier的annotation为中心合并添加，剩下的单独做cluster运算再最后添加
    {
        //在对现有的在地图上显示的annotation为中心做完了annoation合并计算后，剩下的没有被合并的annotation\
        初始化为所有的annotations
        NSMutableArray *annotationsLeftAlone = [NSMutableArray arrayWithArray:annotationsNeedToAdd];
        
        //之前是alone，现在跟新加入的合并成了cluster，这些annoation需要移除,新生成的cluster要将添加
        annotationsToRemove = [NSMutableArray arrayWithCapacity:10];
        NSMutableArray *annotationsToReplace = [NSMutableArray arrayWithCapacity:10];
        
        NSUInteger c = annotationsLeftAlone.count;
        for(id<MKAnnotation> onMapAnn in onMapAnnotations)
        {
            //id<MKAnnotation> onMapAnn = [onMapAnnotations objectAtIndex:i];
            
            NSMutableArray *annotationsToMerge = [NSMutableArray arrayWithCapacity:10];
            
            for(NSUInteger i=0; i<c;)
            {
                id<MKAnnotation> annt = [annotationsLeftAlone objectAtIndex:i];
                if([self isAnnotation:annt closeToAnnotation:onMapAnn])
                {
                    [annotationsToMerge addObject:annt];
                    c--;
                    [annotationsLeftAlone removeObjectAtIndex:i];
                }
                else
                    i++;
            }
            
            //存在要合并到当前annotation的其他annotations
            if(annotationsToMerge.count > 0)
            {
                if([onMapAnn isKindOfClass:[LAGClusterAnnotation class]])
                {
                    LAGClusterAnnotation *clusterAnn = onMapAnn;
                    [clusterAnn addChildAnnotations:annotationsToMerge];
                    
                    MKAnnotationView *v = [super viewForAnnotation:clusterAnn];
                    v.annotation = clusterAnn;
                }
                else
                {
                    [annotationsToRemove addObject:onMapAnn];
                    
                    [annotationsToMerge insertObject:onMapAnn atIndex:0];
                    LAGClusterAnnotation *clusterAnn = [[LAGClusterAnnotation alloc]initWithChildAnnotations:annotationsToMerge groupIdentifier:groupIdentifier];
                    [annotationsToReplace addObject:clusterAnn];
                }
            }
        }
        
        NSArray *annsToAdd1 = [self clusterForOffMapAnnotations:annotationsLeftAlone forClusterGroup:groupIdentifier];
        annotaionsToAddOnMap = [annotationsToReplace arrayByAddingObjectsFromArray:annsToAdd1];
        
    }
    
    if(annotationsToRemove.count > 0)
    {
        [super removeAnnotations:annotationsToRemove];
    }
    
    if(annotaionsToAddOnMap.count > 0)
    {
        [super addAnnotations:annotaionsToAddOnMap];
        
//#warning for debug
//        if(_debugOverlays)
//            [super removeOverlays:_debugOverlays];
//        _debugOverlays = [NSMutableArray array];
//        for(id<MKAnnotation>an in annotaionsToAddOnMap)
//        {
//            if([an isKindOfClass:[LAGClusterAnnotation class]])
//            {
//                LAGClusterAnnotation *clterAnn = an;
//                NSArray *annos = clterAnn.childAnnotations;
//                for(id<MKAnnotation> a in annos)
//                {
//                    CLLocationCoordinate2D crd[2];
//                    crd[0] = a.coordinate;
//                    crd[1] = an.coordinate;
//                    MKPolyline *l = [MKPolyline polylineWithCoordinates:crd count:2];
//                    [_debugOverlays addObject:l];
//                }
//            }
//        }
//        [super addOverlays:_debugOverlays];
//#warning test debug end
        
    }
    
    NSMutableArray *tmpArray = [NSMutableArray arrayWithArray:annotations];
    [tmpArray removeObjectsInArray:annotationsNeedToAdd];
    NSMutableArray *annotationNotToAdd = tmpArray;//不添加到地图的标注点(不在可视区域范围内)
    [_offMapAnnotations addObjectsFromArray:annotationNotToAdd];
    
}

//全部重新刷新
-(void)refreshAnnotationCluster
{
    //优化：放大/缩小/平移 每种情况的算法各不相同
    
    NSArray *onDMapAnns = [super annotations];
    
    NSArray *onMapAnnotationsNeedToReAdd = nil;//需要移除后重新计算并添加的annotations
    BOOL doCluster = NO;
    if([self mapWasZoomed]) //地图放大/缩小，全部刷新
    {
        onMapAnnotationsNeedToReAdd = onDMapAnns;
        doCluster = YES;
    }
    else if([self mapWasPannedSignificantly])//只是平移
    {
        //新区域中，依然有老区域存在的annotation
        NSSet *annotationsKeepOnMap = [super annotationsInMapRect:self.visibleMapRect];
        onMapAnnotationsNeedToReAdd = [onDMapAnns filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"NOT (SELF IN %@)",annotationsKeepOnMap]];
        doCluster = YES;
    }
    
    if(doCluster)
    {
        //移除已经显示在地图上的annotations
        [super removeAnnotations:onMapAnnotationsNeedToReAdd];
        
        //将cluster打散后存放数组
        NSMutableArray *splitedOnMapAnnotations = [NSMutableArray arrayWithCapacity:100];
        for(id<MKAnnotation>an in onMapAnnotationsNeedToReAdd)
        {
            if([an isKindOfClass:[LAGClusterAnnotation class]])
            {
                LAGClusterAnnotation *clusterAnns = (LAGClusterAnnotation *)an;
                [splitedOnMapAnnotations addObjectsFromArray:clusterAnns.childAnnotations];
            }
            else
            {
                [splitedOnMapAnnotations addObject:an];
            }
        }
        
        [_offMapAnnotations addObjectsFromArray:splitedOnMapAnnotations];
        
        NSArray *offMapKeys = _allClusterGroups;
        for(NSString *groupID in offMapKeys)
        {
            NSArray *anns = [self offMapannotationsForGroup:groupID];
            if(anns.count > 0)
            {
                [_offMapAnnotations removeObjectsInArray:anns];
                [self interAddAnnotations:anns toClusterGroup:groupID];
            }
        }
        
        //剩下的不需要cluster的annotations
        if(_offMapAnnotations.count > 0)
        {
            [self addAnnotations:_offMapAnnotations];
        }
        
        
        _lastRefreshMapRect = self.visibleMapRect;
    }

}

#pragma mark- On/Off map record methods
//已经添加到地图上的annotations，包括cluster 和 alone
-(nullable NSArray <id<MKAnnotation>> *)onMapAnnotationsForGroup:(nonnull NSString *)groupIdentifier
{
    NSArray *onMapAnns = [super annotations];
    onMapAnns = [onMapAnns filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"clusterGroupID=%@",groupIdentifier]];
    return onMapAnns;
}


-(nullable NSArray <id<MKAnnotation>> *)offMapannotationsForGroup:(nonnull NSString *)groupIdentifier
{
    NSArray *offMapAnns = [_offMapAnnotations filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"clusterGroupID=%@",groupIdentifier]];
    return offMapAnns;
}

-(nullable NSArray <id<MKAnnotation>> *)annotationsForClusterGroup:(nonnull NSString *)groupIdentifier
{
    NSArray *onMapAnnos = [self onMapAnnotationsForGroup:groupIdentifier];
    NSArray *offMapAnnos = [self offMapannotationsForGroup:groupIdentifier];
    
    NSMutableArray *mArray = [NSMutableArray arrayWithArray:onMapAnnos];
    [mArray addObjectsFromArray:offMapAnnos];
    if(mArray.count > 0)
        return [NSArray arrayWithArray:mArray];
    else
        return nil;
}

#pragma mark- override/extention

- (void)removeAnnotation:(id <MKAnnotation>)annotation
{
    if(annotation)
        [self removeAnnotations:@[annotation]];
}

- (void)removeAnnotations:(NSArray<id<MKAnnotation>> *)annotations
{
    NSMutableArray *mAnnos = [NSMutableArray arrayWithArray:annotations];
    NSArray *allOnMapAnnotations = [super annotations];
    
    NSMutableArray *onMapNeedToRemove = [NSMutableArray arrayWithCapacity:annotations.count];
    //首先尝试移除已经添加到地图上的annotations
    for(id<MKAnnotation> onMapAn in allOnMapAnnotations)
    {
        if([mAnnos containsObject:onMapAn])
        {
            [onMapNeedToRemove addObject:mAnnos];
            [mAnnos removeObject:onMapAn];
        }
    }
    
    if(mAnnos.count > 0)
    {
        //有些annotation可能在cluster的childAnnotations中,如果存在的话要找出这些annotation，
        //并且移除旧的cluster，重新生成新的cluster并添加
        NSMutableArray *annotationsTakeReplace = [NSMutableArray arrayWithCapacity:annotations.count/2];
        NSArray *onMapLeft = allOnMapAnnotations;//这里应该去除上一步中已经移除的annotations以提高效率
        for(id<MKAnnotation> onMapAn in onMapLeft)
        {
            if([onMapAn isKindOfClass:[LAGClusterAnnotation class]])
            {
                LAGClusterAnnotation *clst = (LAGClusterAnnotation *)onMapAn;
                NSUInteger c = mAnnos.count;
                
                NSMutableArray *childAnnsToRemove = [NSMutableArray arrayWithCapacity:20];//一个cluster中要移除的child
                
                for(int i=0; i<c;)
                {
                    id<MKAnnotation> a = [mAnnos objectAtIndex:i];
                    if([clst.childAnnotations containsObject:a])
                    {
                        [childAnnsToRemove addObject:a];
                        [mAnnos removeObjectAtIndex:i];
                        c--;
                    }
                    else
                        i++;
                }
                
                if(childAnnsToRemove)
                    [clst removeChildAnnotations:childAnnsToRemove];
                
                if(mAnnos.count < c)
                {
                    [onMapNeedToRemove addObject:onMapAn];
                    
                    if(clst.childAnnotations.count == 0)
                    {
                        // need to do nothing
                    }
                    else if(clst.childAnnotations.count == 1)
                    {
                        [annotationsTakeReplace addObjectsFromArray:clst.childAnnotations];
                    }
                    else
                    {
                        LAGClusterAnnotation *newClst = [[LAGClusterAnnotation alloc]initWithChildAnnotations:clst.childAnnotations groupIdentifier:clst.clusterGroupID];
                        [annotationsTakeReplace addObject:newClst];
                    }
                }
            }
        }
        
        [super addAnnotations:annotationsTakeReplace];
    }

    [super removeAnnotations:onMapNeedToRemove];
    
    
    //剩下的都是不在地图上的annotation，(也有可能根本就不存在on map 或 off map)移除记录即可
    if(mAnnos.count > 0)
    {
        [_offMapAnnotations removeObjectsInArray:mAnnos];
    }
    
    [annotations makeObjectsPerformSelector:@selector(setClusterGroupID:) withObject:nil];
    
}

-(void)removeAnnotationsForClusterGroup:(nullable NSString *)groupIdentifier
{
    NSArray *annos = [self annotationsForClusterGroup:groupIdentifier];
    if(annos.count > 0)
        [super removeAnnotations:annos];
}

-(NSArray<id<MKAnnotation>> *)annotations
{
    NSArray *onMapAnnotations = [super annotations];
    NSArray *offMapAnns = [self offMapAnnotations];
    
    if(onMapAnnotations)
        return [onMapAnnotations arrayByAddingObjectsFromArray:offMapAnns];
    else
        return offMapAnns;
}

- (NSSet<id<MKAnnotation>> *)annotationsInMapRect:(MKMapRect)mapRect
{
    MKCoordinateRegion r = MKCoordinateRegionForMapRect(mapRect);
    
    NSSet *annos = [super annotationsInMapRect:mapRect];
    
    NSMutableSet *offMapAnns = [NSMutableSet set];
    for(id<MKAnnotation> a in _offMapAnnotations)
    {
       if(isCoordinateInRegion(a.coordinate, r))
       {
           [offMapAnns addObject:a];
       }
    }
    
    if(offMapAnns.count > 0)
    {
        [offMapAnns setByAddingObjectsFromSet:annos];
        return [NSSet setWithSet:offMapAnns];
    }
    else
        return annos;
}

// Currently displayed view for an annotation; returns nil if the view for the annotation isn't being displayed.
- (nullable MKAnnotationView *)viewForAnnotation:(id <MKAnnotation>)annotation
{
    MKAnnotationView *v = [super viewForAnnotation:annotation];
    if(!v && ![_offMapAnnotations containsObject:annotation])
    {
        LAGClusterAnnotation *cluster = [self clusterForAloneAnnotation:annotation];
        v = [super viewForAnnotation:cluster];
    }
    
    
    return v;
}

#pragma mark-
-(NSArray<id<MKAnnotation>> *)offMapAnnotations
{
    return [NSArray arrayWithArray:_offMapAnnotations];
}

//找出aloneAnnotation所属的cluster
-(LAGClusterAnnotation *)clusterForAloneAnnotation:(id <MKAnnotation>)aloneAnnotation
{
    LAGClusterAnnotation *cluster = nil;
    NSArray *onMapAnns = [super annotations];
    for(id<MKAnnotation> onMapAn in onMapAnns)
    {
        if([onMapAn isKindOfClass:[LAGClusterAnnotation class]])
        {
            LAGClusterAnnotation *clst = (LAGClusterAnnotation *)onMapAn;
            if([clst.childAnnotations containsObject:aloneAnnotation])
            {
                cluster = clst;
                break;
            }
        }
    }
    
    return cluster;
}


#pragma mark- Helper



-(BOOL)isAnnotation:(id<MKAnnotation>)annotation1 closeToAnnotation:(id<MKAnnotation>)annotation2
{
#warning todo 在初始化的时候就将像素距离转换成坐标距离，这里就只需要判断坐标距离，不用每次判断都将坐标转换成像素，提升运算速度
    CGPoint p = [self convertCoordinate:annotation1.coordinate toPointToView:self];
    CGPoint p1 = [self convertCoordinate:annotation2.coordinate toPointToView:self];
    
    CGFloat deltaL = _clusterRadium;
    
    BOOL close = NO;
    
    if(fabs(p.x-p1.x)<=deltaL && fabs(p.y-p1.y)<=deltaL)
        close = YES;
    
//    if(sqrt(pow((p.x-p1.x),2) + pow((p.y-p1.y),2)) <= deltaL)
//        close = YES;
    
    
    return close;
}



- (BOOL)mapWasZoomed;
{
    BOOL ret = (fabs(_lastRefreshMapRect.size.width - self.visibleMapRect.size.width) > 50.0f);
    
    //llf added 2017.02.14
    if(ret)
    {
        if(self.camera.heading > 0.0)
        {
            float lastZoomLevel = [self zoomLevelForMapRect:_lastRefreshMapRect];
            float curZoomLevel = self.zoomLevel;
            
            ret = (fabs(curZoomLevel - lastZoomLevel) >= SCALED_ZOOM_DELTA);
        }
        
    }
    return ret;
}

- (BOOL)mapWasPannedSignificantly;
{
    MKCoordinateRegion lastRegion = MKCoordinateRegionForMapRect(_lastRefreshMapRect);
    
    CGPoint lastPoint = [self convertCoordinate:lastRegion.center toPointToView:self];
    CGPoint currentPoint = [self convertCoordinate:self.region.center toPointToView:self];
    
    BOOL ret = ((fabs(lastPoint.x - currentPoint.x) > MAP_EXTENTION_DELTA_WIDTH) ||
                (fabs(lastPoint.y - currentPoint.y) > MAP_EXTENTION_DELTA_HEIGHT));
    
    return ret;
}




@end
